A non-empty set V of objects called vectors, along with rules for
adding any 2 vectors v and w in V
multiplying any vector v in V by any scalar r in
Must satisfy closure properties
vector addition:
scalar multiplication:
Must satisfy the following axioms for vector addition
Associative
Commutative
An additive identity exists
a zero vector 0 s.t. 0 + v = v,
An additive inverse exists
an additive inverse s.t. v + (-v) = 0
Must satisfy the following axioms for scalar multiplication
Distributes over vector addition
Distributes over scalar addition
Associative
A multiplicative identity exists
Note: vectors could refer to matrices, polynomials, functions, power series, etc.
Q Let with usual operations. Is V a vector space?
A Let . Suppose
Check closure under addition:
Check closure under scalar mult:
Usual ops A1-A4, S1-S4 all hold V is a vector space.
Q Find the zero vector in where addition is defined by
A
To define a vector space, need to specify 4 parts:
Objects that make up the set V
The field where scalars come from (if the field of scalars is the set of real #s, then V is a real vector space)
How to add vectors
How to multiply scalars with objects in V
The below sets with given rules for are vector spaces.
Notation
Definition
set of vectors of length n with real entries
set of vectors of length n with complex entries
set of all polynomials in x with real coefficients
with degree n
set of all real matrices of size m(rows) by n(columns)
set of real-valued functions with domain
Thm 3.1 (Elementary Properties of Vector Spaces)
Every vector space V has the following properties:
is unique for all vectors in V
is unique for each vector in V
Proof
Suppose 2 zero vectors, and . Then for all v in V, and .
Since , sub into
Since , sub into
is unique
By definition, . Suppose .
Any additive inverse is unique
If =
Then =
Equate LHS & RHS
.
Equate LHS & RHS
.
Equate LHS & RHS
W2 (3.2)
Vector Space vs Real Space
Concepts for real space extend to vector spaces
Except that vector spaces could be spanned by an infinite set of vectors
E.g.The vector space P of all polynomials is spanned by the set of monomials
M is a basis for P M spans P P = span(M)
M generates P and so P is NOT finitely generated
Def. Linear Combination
is a linear combination of if there scalars s.t.
Note linear combinations must be of a finite number of vectors (otherwise called Schauder basis)
Def. Span
is the set of all linear combinations of elements in X, where X is a subset of V.
If , then the vectors in X span or generate V.
QIs ? Assume standard polynomial addition and scalar mult.
ACheck if can be written as
(derived using the coefficients)
Unique solution, so yes, is in the span of the set.
Thm (Span of a subset is a subspace)
If is a non-empty subset of vector space , then is a subspace of .
Proof
Since X is non-empty, sp(X) must be non-empty
Let , let
Since s.t.
Then
Non-empty, closed under additional and scalar mult -> span of X is a subspace of V.
E.g. Let
, which is still a linear combination of vectors in X, so we have closure under addition.
, which is a multiple of - again - linear combinations of vectors in X, so we have closure under mult.
Corollary (Not covered in class)
is the smallest subspace of containing all the vectors in .
Proof
Let M be the smallest subspace of V containing
Claim:
Since for all ,
we have by definition of span, so
Since and every subspace is a vector space with closure properties,
we have , so
Thus
Def. Subspace
Let be a vector space and a subset of . Then is a subspace of if is a vector space using the defined ops for .
E.g. Counter examples
Subsets of that are closed under addition but not scalar multiplication:
if multiply by r=-1, the result
if multiply by r = 0.5, the result
if multiply by r = , the result
Subset of which is closed under scalar multiplication but not addition:
Ways to prove is a subspace
Show is a vector space using the definition (too much work)
Use the span theorem (probably easiest)
Use the subspace test
Thm 3.2 (The Subspace Test)
A subset of is a subspace of if
The zero vector (Sometimes omitted as it is implied by 3)
is closed under vector addition
is closed under scalar multiplication
Shortcut for 2 & 3: check both at the same time by using
Q Is the set of nxn invertible matrices a subspace of (the vector space of all nxn matrices)?
A No. The sum of 2 invertible matrices may not be invertible (violates 2).
Also, the 0 matrix is not invertible (violates 1).
Def. Linear (In)dependence
Let X be a set of vectors in a vector space V. (X can be an infinite set.)
A dependence relation in X is an equation of the form with some where for i = 1, … , k.
If such a dependence relation exists, then X is linearly dependent. Otherwise, X is linearly independent.
If X is finite, then the following definition applies:
The set with is linearly independent if implies
Note: { } is independent (vacuous statement)
There is no collection of vectors from { } satisfying a dependence relation because there is nothing in the set at all
sp({ }) = {}
Convention: the empty summation is taken to be its additive identity ().
Q Suppose is linearly independent. Prove is also linearly independent.
A Assume
WTS this implies
Since is linearly independent,
QConsider F, the vector space of all functions from (with usual operations).
Is linearly independent?
AX is linearly dependent since
Q Is linearly independent?
A X is linearly independent.
Assume holds
(The equation must hold for since it holds for all x.)
X is linearly independent
If we find a non-trivial solution (a or b or both != 0), NO conclusion can be made.
To generate more equations, we can take derivatives first then plug in points.
To check if a set is linearly independent:
If it cannot be observed, set up the dependence relation equation as the first step.
If the set spans a space with a dimension lower than the cardinality of the set (i.e. dim(span of the set) < |set|), then the set cannot be linearly independent.
If given a set of polynomials, put the coefficients as column vectors in a matrix, reduce to REF, and solve the system of equations.
Other ways:
create a system of equations by plugging in dif values of x (# values = # unknowns) and solve
differentiate the dependence relation, plug in the same value of x each iteration
expand and rearrange in terms of a linear independent set, then the coefficients must be 0, solve
see if the set contains the zero vector
Def. Basis
A subset X of V is a basis for V if:
X spans V
X is linearly independent
Def. Dimension
Let V be a finitely generated vector space. The number of elements in a basis for V is the dimension of V, dim(V).
Note: When giving definitions, "a" and "the" imply different things - "the" implies that the object described is unique.
Q Is dimension well defined? I.e. Can 2 bases have different sizes?
A It is well defined since any 2 bases of V must have the same number of elements. This is true by the following theorem.
Thm (Dimension and Linear Independence)
Suppose that is a vector space of dimension n. Then any subset X with size greater than n is linearly dependent.
Proof
Since V has dimension n, there must exist a basis of size n:
Let with
Since is a basis, each can be written as a linear combination of elements of : .
i.e.
Assume a vector such that
Since m > n, we have more unknowns than equations, so there must be a non-trivial (non-zero) solution, i.e. the lambda vector must be non-zero.
Setup dependence relation:
cannot all be 0, and cannot all be 0, so there exists at least one non-zero coefficient in the dependence relation so X is not linearly independent.
E.g. (with usual operations) has a standard basis of and
E.g. (with usual operations) has
E.g. Diagonal matrices (with usual operations) has
E.g. (with usual operations) has a standard basis of of
Note The degree of the zero polynomial is conventionally -1 or - (not defined in the textbook).
Note The subset is a subspace of dimension 0, since its basis is { } or which has dimension 0.
Any set containing is dependent because has a solution
So its basis cannot be since a basis cannot be a linearly dependent set
Thm (Lin Ind Set Basis Spanning Set)
Every linearly independent set of vectors in can be enlarged to a basis of by adding vectors from any fixed basis of . (Be careful which ones you add - to preserve independence.)
Any spanning set for can be cut down (by deleting vectors) to a basis of . (Be careful which ones you delete to preserve span.)
Thm 3.3 (Unique Representation)
Let be a set of non-zero vectors in a vector space .
Then is a basis for iff each vector in can be uniquely expressed as where and .
Proof for Thm 3.3
When B is finite:
Suppose B is a basis (so it is lin ind) and that can be expressed the following 2 ways:
B is linearly independent, so has unique representation.
() Suppose every vector can be uniquely expressed in terms of B. This implies V = span(B).
can be uniquely expressed in terms of B, so B is lin ind.
B spans V and is linearly independent, so B must be a basis.
When B is infinite:
pad two different expressions of a vector (in terms of a finite number of elements in B) with zeros
so that the two expressions use the same finite subset of vectors from B
As a result, B now represents this finite subset (of the infinite set) used in our representations of the vector v.
Def. Finitely Generated
V is finitely generated if it is the span of a finite set, i.e. if where X is finite.
Q Which of these vector spaces is finitely generated?
The vector space of all functions ?
The vector space of all polynomials.
The vector space of all polynomials of degree less than or equal to n.
The vector space of all 2×2 matrices.
A 3 is finitely generated as it is the span of the finite set
4 is finitely generated as it is the span of the finite set of 2x2 matrices where the ij-th entry = 1 and all other = 0
Thm (Shortcut for proving basis)
Let B be a set of m vectors from V. If |B| = dim(V), then showing one of (B is lin ind, B spans V) will suffice.
Proof (If , then any lin ind B is a basis of V.)
B is a basis for V if it spans V and is lin ind. Lin ind is given, so just need to show it spans V.
Suppose that B does not span V. Then .
This contradicts the fact that any set with >m elements cannot be lin ind in a vector space of dimension m.
Proof (If , then any B spanning V is a basis of V.)
B is a basis for V if it spans V and is lin ind. We know B spans V, so just need to show lin ind.
Suppose that B is not lin ind. Then at least 1 of its elements can be written as a lin combo of the other elements.
Delete that element to get , which would have the same span as B. B' would have m-1 elements.
Continue deleting until lin ind. Since the set has the same span as B, it must be a basis for V.
However, it would have <m elements, which contradicts .
Q Let . Show is a subspace of and find a basis for .
A Any satisfies
Consider , then where
Plugging in a, b, c, we have
Then
By Span Theorem, is a subspace of .
is linearly independent, so it is a basis of and .
W3 (3.3, 3.4 pg. 213-216)
Recall: If is a linear transformation, then T is induced by a matrix where is the standard basis of . Then for we have .
Ordered Bases
We can give an order to every basis. Note: To emphasize the basis is ordered, we use ( ) instead of { }.
E.g. has 6 ordered bases using {} =
They are:
Def. Coordinate Vector
Let be an ordered basis for a vector space V.
Suppose , then the coordinate vector of relative to the basis B is defined as
By the unique representation theorem, this vector is well defined.
E.g. Let
If , then
If , then
Thm (Coordinatization of Vector Spaces)
Any finite dimensional vector space with dimension can be coordinatized to look like .
We choose an ordered basis ().
Since each vector has a unique coordinate vector relative to B, there is a 1-1 correspondence between objects in and vectors in
We may now work over instead of
To see this, we verify that vector space operations are mirrored by operations on coordinate vectors in
Proof
We show that for , vector space ops = ops:
(1) Show that
Suppose (by unique representation theorem) we have vectors v and w:
Then
(2) Show that
Def. Isomorphic
When we rename vectors in using coordinates, the vector space of coordinates (i.e. ) has the same structure as .
If appears structurally identical to , we say and are isomorphic, or .
E.g.,
Thm (Dimension Determines Structure)
If is a vector space over and , then is isomorphic to
Hence, to know the structure of a vector space (no matter how complicated are), we only need to know its dimension - i.e. and are isomorphic dim(V) = dim(W)
This is contrary to other mathematical structures like groups, rings, etc.
Def. Linear Transformation
Let V and W be vector spaces, then the function is a linear transformation if
T preserves addition
For , we need
T preserves scalar multiplication
For all , we need
It is clear to see that T preserves linear combinations:
Fact 2 lin transf are the same if they have the same value at each basis vector
ProofLet T and T' be 2 linear transformations such that
Let , then and such that
Thus are the same transformation
Other facts:
T preserves zero vector
Proof
T preserves additive inverse (and thus substraction)
E.g. defined is a linear transformation
Recall
T preserves addition
T preserves scalar mult
E.g. defined is not a linear transformation
T preserves addition
Consider A = B = I
Recall Determinant of a diagonal matrix is the product of the diagonal entries
The above are not equal if n > 1
T preserves scalar mult - no need to check
E.g. Derivatives and integrals are linear transformations
Def. Domain, Codomain
Let and be vector spaces and be a linear transformation.
Then is the domain of , is the codomain of .
Def. Image, Inverse Image
The image of T (or image of V under T, in blue) is a subspace of W:
Labelling as W', then the inverse image of W' under T is a subspace of V:
Def. Range, Kernel / Null Space
is the range of T (also image of V under T).
The kernel of T (or inverse image of under T, in green) is a subspace of V:
It is clear to see that is solution set of the homogeneous transformation equation
Thm (Rank-Nullity)
Intuition: each dimension (or component) in V either gets preserved or compressed to
Proof
Let be a basis for so
Extend it to a basis for so
We know , just need to prove
Do so by finding a basis for the image:
By Unique Rep Thm, we can write any as ,
so
WTS is lin ind: set up the dependence relation
since T is linear
since is a basis for
since is lin ind (it is a basis)
So is lin ind, which means it is a basis for the image.
Thus
Technique to Find Bases for Image(T)
find a basis for
extend it to a basis for V
apply T to what's been added to get a basis for
E.g. Let and be a lin transf defined by
Find a basis for using the above technique.
Find a basis for
Extend it to a basis for V
Extend by adding elements of the standard basis for
(This is not the only way)
Apply T to what's been added to get a basis for
E.g. Let be the linear transformation defined by . Find a basis for the image of and a basis for the kernel of .
Method 1: finding a matrix rep rel. to ordered bases and observing the null/column space
Let be an ordered basis for .
Then the matrix for relative to is
A basis for the null space of is , thus, a basis for is .
Note: dim(ker(T)) = dim(null space(A))
A basis for the column space of is , thus, a basis for is
Method 2: finding a basis for the kernel of T and extending it to get a basis for the image of T
so to find the kernel, we need to find p such that
Using ,
Expand and simplify to obtain
(Or don't expand and obtain the corresponding system )
Thus, is a basis for .
Now extend this to a basis for — add to the set.
This implies that a basis for is
Def. Row Space
Motivation Suppose U is a subspace of with a basis of . What operations can be performed on this basis while preserving its span and linear independence?
Swap 2 vectors
Multiply a vector by a non-zero scalar
Add a scalar multiple of 1 vector to another
If are the rows of a matrix, these are simply elementary row operations!
If is a m x n matrix, then the row space of A is the subspace of spanned by its rows, denoted row(A)
Facts
Elementary row operations do not change the row space
In general, the rows of A may be linearly dependent
Thm The non-zero rows of any REF is a basis for row(A)
E.g. Find a basis for using row space
By the theorem, row(A) has a basis of has a basis of
E.g. Find dim(row(A)) if
row reduces to is a basis
So dim(row(A)) = 2
Def. Column Space
If A is a m x n matrix, then the column space of A is the subspace of spanned by its columns, denoted col(A);
col() = row(), so a basis of can be computed by reducing to REF
Note
E.g. Find a basis for col(A) if
row-reduces to
Since (col 2) = 2(col 1), and (col 4) = 3(col 1) + 5(col 3),
a basis for col(A) is the other 3 columns:
Note We can't use columns of the REF for a basis, since row operations mess up the vectors!
Strategy for finding basis of row(A) and col(A)
reduce A to REF = R
A basis for row(A) is formed by rows of R containing leading 1's
A basis for col(A) is formed by cols of Acorresponding to cols of R with leading 1's
Def. Rank
The rank of a m x n matrix is the number of leading 1's in its REF, and
Both of the below have
(1)
columns of span ; rows of are independent in
(2)
rows of span ; columns of are independent in
E.g. Can a 5 x 6 matrix have linearly independent rows/cols?
The matrix would reduce to
Cols cannot be linearly independent since each column has 5 entries (so ) but there are 6 columns. Only 5 are needed to span . The 6th column can be written as a lin combo of the first 5. The 6th variable can be anything.
Rows can be linearly dependent or independent.
Note The converse: if # rows > # columns, the rows must be lin dep, the cols may be lin dep.
E.g. Let be m x n with , prove
by definition, and , so
E.g. Let be a 5 x 9 matrix, prove
by definition, and
Note rank-nullity theorem was used here: for ,
W4 (remainder of 3.4)
Thm 3.7 (Lin transf preserves subspaces)
Let V and V' be vector spaces and let be a linear transformation.
Proof (If is a subspace of , then is a subspace of )
Subspace test:
WTS contains the zero vector
Since is a subspace,
WTS , where and so
Since is a subspace,
WTS , where and so
Since is a subspace,
Proof (If is a subspace of , then is a subspace of )
WTS contains the zero vector
Since is a subspace,
WTS , where , and so
Since is a subspace,
WTS , where and so
Since is a subspace,
Def. Onto & 1-1
Let V and W be vector spaces and is a linear transformation
Onto (surjective)
1-1 (injective)
for any such that
for any , or
all elements in W have been mapped to at least once
all elements in W have been mapped to at most once
has at least 1 solution
has at most 1 solution
is consistent
has a unique sol'n or is inconsistent
A has a pivot in every row
A has a pivot in every column
The columns of A span W
The columns of A are lin ind i.e. has only the trivial solution i.e.
T preserves spanning sets: Suppose then
T preserves lin ind: Suppose is a lin ind subset of V, then is a lin ind subset of W.
dim(range of T) = dim(W)
dim(range of T) = dim(V)
Note If T is both onto and 1-1, then it is bijective (and it must be an isomorphism, so it's invertible).
For bijective has a unique solution (i.e. A has a pivot in every row and column)
Thm (Extra TB notes)
Let for some particular vector in V.
Then the solution set of is the set (h is the solution to the homogeneous transf eq)
This means:
If , then has at most 1 solution which is , so T is 1-1
If T is 1-1, then has only the trivial solution by definition, so
So 1-1 follows from this.
E.g. Show that the solution of is the set
(So , and )
Want to find such that , i.e. find y such that
By inspection, try . Then we have which can't be true
So kill off the with , then we have which holds
So we've found the solution:
The homogeneous transformation eq in this case is
Its general solution is is a basis for
The general solution for is thus
Thm (Compositions of lin transf is a lin transf)
Let and be linear transformations (U, V, W are vector spaces).
Then is also a linear transformation
Proof Let
WTS
Def. Invertible Transformation
A linear transformation is invertible if there is a linear transformation such that , where is the identity transformation mapping vectors from W to W as
is the inverse for T (using "the" because it is unique).
Fact T is invertible T is an isomorphism
Thm (T is invertible if A is invertible)
Suppose that is a basis for the vector space , is a basis for the vector space , and is a linear transformation. Show that is an invertible transformation iff the matrix representation (or denoted by of wr.t. the bases and is an invertible matrix.
Suppose T is invertible, then such that .
Let be the matrix representation of with respect to the bases and
Since and , is an invertible matrix.
Assuming is an invertible matrix, there must be a matrix such that ,
Let be the matrix rep of the linear transf. , i.e. .
Then , and (reads identity transf. on ), so S is an inverse for T, and T is invertible.
Thm 3.8 (T is invertible iff 1-1 and onto)
Proof Suppose
(): invertibility implies 1-1 & onto
Since T is invertible, such that for all . This means T must be onto .
, so . Hence T must be 1-1.
(): 1-1 & onto implies invertibility
Since T is onto , such that for all . Since T is 1-1, this must be unique.
Define as , where is that unique vector satisfying
Then
and
Hence T is invertible.
Remains to show that is indeed a linear transformation:
Preserves addition
Preserves scalar mult
Def. Isomorphism
A linear transformation is an isomorphism if it is 1-1 and onto.
E.g. Prove
Construct a linear transformation that is 1-1 and onto:
Consider
Show linearity (T preserves addition and scalar mult)
Show 1-1 (by showing )
Show onto
For any polynomial , we can find a matrix in that maps to it, namely
Thm (Iso proof shortcut if same dim)
Let V, W be finite dimensional vector spaces and a linear transformation.
If , then T is an isomorphism iff T is OR(onto, 1-1).
Prove using the rank nullity thm:
same dim & 1-1 invertible
If , and is 1-1, then
By the rank nullity thm, .
And since is a subspace of which also has dimension , we have that . Hence, T is onto.
Since T is both 1-1 and onto, it must be invertible.
same dim & onto invertible
If , and is onto, then
By the rank nullity thm, is 1-1.
Since T is onto and 1-1, it must be invertible.
Thm 3.9 (Coordinatization is an isomorphism)
Let V be a finite dimensional vector space with ordered basis
T is 1-1 since the coordinate vector uniquely determines
T is onto since the range of T is all of
Note The isomorphism of V with is not unique, since there is a corresponding isomorphism for each choice of an ordered basis of V.
W5 (7.1, 7.2)
Def. Standard Matrix Rep of Lin Transf
Recall concepts for
A transformation is linear iff it has the form .
The matrix is the standard matrix representation of
The action of T on unit vectors determines the structure of A
Properties of T (onto/1-1) are deeply related to existence & uniqueness of solutions to or
Q Find the standard matrix rep of
A For , the standard matrix rep is given by
Since ,
Shortcut for finding A: instead of calculating each col vector by transforming , just write out the coefficients of the transformed input as row vectors
Now, how do we find the matrix rep of , where are non-Euclidean vector spaces?
E.g. Define by
To represent with a matrix, we start with an ordered basis for each of and
For
For
Since it is easier to work over , we use the following coord. transformations:
defined by
defined by
defined by
This way, we can write T as a composition of linear transformations:
(since , illustrated below)
Since T is a composition of lin transf, it must be linear itself, so find the standard matrix for
is said to be the matrix of with respect to B and C.
Also, A is invertible (it has a non-zero det) T is invertible T is an isomorphism.
is also an isomorphism.
Matrix Rep Notation
Matrix rep of T relative to and can be denoted as , , or
The following denote the matrix rep of T inverse
The following denote S composed with T illustrated above
(matrix for ) = (matrix for S)(matrix for T)
The following denote the change of basis matrix illustrated below
where is the identity transformation
Def. Matrix of T Rel. to Basis B
Let V be a finite dimensional vector space with ordered bases
Let be a lin transf, then is the matrix of T relative to basis
Def. Matrix of T Rel. to Bases B and B'
Let V and V' be finite dimensional vector spaces with ordered bases and .
Let be a lin transf and be the lin transf such that .
I.e. transforms (coord. of rel. to B) into the coord. of transformed rel. to B'
Then the matrix rep of T relative to and is the m x n matrix
I.e. A is the coordinates of the transformed basis vectors (of ) relative to
And so
I.e. the coord. of any transformed vector can be obtained by: multiplying A (coord. of transformed basis vectors rel to B') with its coord. relative to B
Note is the matrix rep of relative to .
Prove: j-th column of A =
Since the coord vector of rel. to B is given by
the coord vector of rel. to B is given by so
j-th column of A
E.g. Find where , and use it to compute , given
E.g.Consider defined by
Let be an ordered basis for ,
and an ordered basis for
Find
Def. Change of basis matrix
If we have a vector space V with basis B, we can find a new basis B' using the matrix and the change of basis formula
I.e. (coord vec of in new basis) = (change of basis matrix from B to B') (coord vec of in old basis)
Note Recall from thm 3.10. Note its similarity to the change of basis formula.
Note
E.g. Find the change of basis matrix for
If , then row reduce the matrix [new basis vectors | old basis vectors] to find :
E.g. Let . Find where and .
Also find where
Note: is essentially since for i = 1,
Then
Motivation for next topic
Consider where is the derivative
If , then differentiate to get
If , then differentiate (and decompose):
so
use different bases, but represent the same transformation . Their similarities are :
both not onto with rank 2
both have det = 0, trace = 0
both have the eigen values {0, 0, 0}
These similarities are not a coincidence. Similar matrices have similar properties.
Def. Similar Matrices
Let A, B be square matrices, then A is similar to B if there is an invertible C such that
A and B would have the same rank, determinant, eigenvalues, trace, and change of basis matrix.
Note A and B are similar iff they are the matrix reps of the same linear transformation relative to different bases. (thm 7.1)
Thm 7.1 (Basis Change in A Vector Space)
If we have a finite dimensional vector space with bases , and a linear transformation , then the matrix reps for T, and must be similar, so where
Rearranging, we have which is illustrated below (right + down = down + right)
Since , we have
E.g.
Let
Find such that
Shortcut to find Matrix Rep (Add basis E)
In the above, if we let , and let have bases and . Then and we have the following
Rearrange the above to get:
or
E.g. Let be polynomials, be a linear transf. defined by
Find if
Let be the standard basis , then
Apply T to basis and decompose/express as lin combo:
so
Recall
So to find , row reduce
We have found (and to find , use )
Thm (Basis Change between 2 Vector Spaces)
For a linear , where has ordered bases , and has ordered bases , we can change coord from using
or
Def. Eigen Values/Vectors
Given a transformation, an eigen vector is a non-zero vector that only gets stretched/scaled by a factor (not morphed)
To obtain the eigen value, solve the equation that arises from det = 0 (last line), called the characteristic polynomial
To obtain the eigen vectors, plug the eigen values back into the second to last line, and solve the system
Let be linear, be a vector space
is an eigen value of if a non-zero such that
this is the eigen vector of T corresponding to
direction of is unchanged/invariant under T
If is an eigen value of A corresponding to , then is an eigen value of corresponding to
Fact If , then eigen values of T are eigen values of the standard matrix rep of T
E.g. Consider vector space and basis .
Find the eigen values and eigen vectors of defined by
Find matrix for T relative to E:
Find eigen values by performing cofactor expansion down the 3rd column:
Eigenvalues
Eigenvectors for
Eigenvectors for T
[-3, 6, 1]
[0, 0, 1]
[2, 1, 1]
Note If the basis consists of eigenvectors for , i.e., , then the matrix rep of T relative to is
Def. Eigen Space
If is an eigen value of A, then the eigen space of A , denoted , is the set of eigen vectors corresponding to plus the zero vector (which isn't categorized as an eigenvector, even though it has the properties of one).
Note so it is a subspace of n-space (either or ).
Def. Alg & Geo Multiplicities
Algebraic multiplicity of = its multiplicity (as a root) in the characteristic polynomial
Geometric multiplicity of =
Def. Diagonalizable
Def. is diagonalizable if it is similar to a diagonal matrix
is said to diagonalize
Note The diagonal entries of D are the eigenvalues , and the column vectors of P are the eigen vectors
Thm is diagonalizable
has n linearly independent eigen vectors (i.e. enough eigen vectors to form a basis for )
sum of (alg mult of eigen values of A) = n, and each eigen value has geo mult = alg mult
sum of (geo mult of eigen values of A) = n (so if distinct eigen values, then
where means direct sum, e.g. )
E.g. Consider defined by , e.g. . Is T diagonalizable?
Let be a standard basis of
Then
Does there exist 3 lin ind. eigen vectors for the matrix rep of T?
The characteristic polynomial of is
So is an eigenvalue for with algebraic multiplicity 3 ()
And eigenvectors are
So the eigenspace and the geometric multiplicity of eigenvalue 0 is 1
Since there isn't enough eigenvectors, the sum of (vector space), so T is not diagonalizable.
Note If T is diagonalizable, then it is easy to compute powers of T, e.g. T(T(V)) by finding which is the (diagonal) matrix rep of T relative to the basis of eigen vectors (denoted B') and taking the appropriate power of the matrix .
W6 (6.1)
Def. Orthogonal
Let and be vectors.
Their dot product is where is the angle between x and y.
Since when , they are said to be orthogonal (perpendicular) if
The length of is and
A unit vector in the direction of is obtained by dividing by its length:
Def. Orthogonal Set
The set is an orthogonal set if each is not the zero vector and every pair of distinct vectors is orthogonal.
Note not included so that certain properties hold (e.g. orthogonal sets are lin ind.)
Proof Orthogonal sets are linearly independent.
WTS only has the trivial solution
Take dot prod of eq'n with :
Def. Orthonormal Set
A set is orthonormal if it is orthogonal and
E.g.
Each pair has dot prod = 0 and each vector has length 1, so this set is orthonormal subset of
Def. Normalize
To normalize an orthogonal set, divide each element by its length to turn it into an orthonormal set
Def. Orthogonal Complement
Let be a subspace of . The orthogonal component of is
E.g. If is a plane through the origin in , then is the line through the origin perpendicular to the plane
both line and plane are vector spaces assuming they pass through the origin
every vector in the plane is orthogonal to every vector on the normal line
Facts Let be a subspace of
is a subspace of
and
If then (no need to check every vector in W, just check its generating set)
Each vector in can be expressed uniquely in the form where
Thm (Ortho Complement of Row/Col Space )
Let be an m x n matrix, then
Proof Let
is in is orthogonal to every row of
is in is orthogonal to every row of
Technique to Find Ortho Complement
Find a matrix whose rows are vectors that span
Find
E.g. Find if
for i = 1, 2, 3.Solving the 3 equations, we have
Solving the 3 equations is equivalent to just writing the 's in a matrix:
which row reduces to
so
Check that and that
W8 (6.2 - 6.4)
Def. Projections (Textbook Def)
Let L = span{} be a line through the origin
Take a vector and project it onto
We can decompose into the sum of 2 vectors: 1 parallel to L and 1 perpendicular to L
Let be a vector in and W a subspace of . Let , then is the projection of onto
Steps to find projection of onto
Select a basis for
Find a basis for
Find coord. vector of relative to basis (proof below) so that
Then
Proof If W is a subspace in , is a basis for W, and is a basis for , show that is a basis for .
NTS it spans (which it clearly does), and is linearly independent.
Set up the dependence relation
Suppose
By the dep. rel, we also have that
Since , (since )
Thus, and
Since and are linearly independent,
is lin ind.
Note If instead, is an orthonormal basis for W, and is an orthonormal basis for , then is an orthonormal basis for . Thus, every can be written uniquely in terms of as
Proof (that coefficients are )
If , then
Def. Projections (Alternative Def)
Let be a subspace of with an orthogonal basis. Then the projection of on W is or
Properties Let be a subspace of and . Then
is the unique vector in W closest to
Proof WTS for all , i.e. minimized when
iff
E.g. Let . Find the vector in closest to
Since W is the span of an orthogonal set, the answer is by the projection theorem.
Observe that the is just with its first value replaced with 0. This makes sense since W is the span of 2 vectors with x = 0, so it is like projecting onto the y-z plane. Hence another (simpler) way to approach this problem would be to choose the basis as the standard basis of the y-z plane
Def. Gram Schmidt Algorithm
Every subspace of has an orthonormal basis.
Let be a basis for . The Gram Schmidt algo generates an orthogonal basis for .
Illustration for :
For convenience, we can scale to remove fractions during the algorithm.
To get an orthonormal basis, we divide each vector by its length at the end.
Def. Orthogonal Matrix
A square matrix Q is said to be orthogonal if any of the following is true
its columns form an orthonormal set
Note If A is not square, then . This chain of equality only holds if A is square. (They do have the same non-zero eigen values however.)
Properties
both and are orthogonal
Proof is orthogonal
Proof is orthogonal
Since is orthogonal, rows of W also form an orthonormal set
det(Q) = (so orthogonal matrices are rotations or reflections)
Proof
Proof
Proof
The angle between non-zero vectors and = the angle between and
Proof
If is an eigenvalue of Q, then (all eigs are on the unit circle in the complex plane)
Proof so but alsoso
If and are orthogonal, then so is
Proof
Thm (Relation to Change of Basis)
If is an orthonormal basis of ,
then the change of basis matrix rel. to is , which is an orthogonal matrix.
So
and
E.g. Let be an ordered orthonormal basis for , and let be the coordinate vector of a vector in relative to this basis. Find .
Let be the standard basis for and , then
Def. Orthogonal Transformation
A linear transformation is orthogonal if
(T is orthogonal its matrix is orthogonal)
Def. Projection Matrix
Let be a subspace of , then defined by is a linear transformation. The standard matrix for is called the projection matrix for the subspace .
Steps (to find a projection matrix for subspace )
form a matrix using vectors from 's basis: so that is the column space of
then is the projection matrix for the subspace and
If is an orthonormal basis,
E.g. Let . Find the projection matrix for W and
Let . Note that the columns are orthonormal, so A is orthogonal, i.e.
Then and
Proof(for )
Note that W = col(A), so all vectors in W can be written as
such that
is perpendicular to vectors in W, which all have form
Properties
Every n x n matrix that is both symmetric and idempotent is a projection matrix.
P is symmetric if
P is idempotent if
E.g. Find all invertible projection matrices.
Since projection matrices are idempotent,
If is invertible, then multiplying both sides of by gives .
W9 (9.1, 9.2)
Def. Least Squares
Let A be an m x n matrix. could have no solution, i.e. if is not in col(A).
Then the best "approximate solution" to is the least squares solution , where
minimizes error , which is the sum of squares of the errors in the m equations (when )
If no solution, then multiply by to get , and solve for .
Justification Look for for which .
E.g. Find the line closest to points (0, 6) (1, 0) and (2, 0)
y = mx + b so
So y = -3x + 5 is the line of best fit
Note is invertible by the following thm.
Thm (Invertibility, Lin Ind, and Uniqueness)
Let A be an m x n matrix and . Then the following are equivalent:
has a unique least squares solution
columns of A are linearly independent
is invertible
Def. Symmetric Matrices
A symmetric matrix always has real eigen values and is always diagonalizable (by a real orthogonal matrix).
Properties
Eigenspaces of a symmetric matrix are mutually orthogonal.
Thus, symmetric matrices have n mutually perpendicular eigen vectors.
Proof Let be an eigen value and be a real matrix.
Then for some
Since is real,
LHS:
RHS:
Equating LHS and RHS, we have that is real
Def. Orthogonally Diagonalizable
A square matrix A is orthogonally diagonalizable if there is an orthogonal matrix and a diagonal matrix such that
Note For a real n x n matrix A, symmetric orthogonally diagonalizable
E.g. is diagonalizable but not orthogonally diagonalizable since it is not symmetric.
Steps to orthogonally diagonalize a matrix :
Find the eigen values and eigen vectors
Form a basis with the eigen vectors and normalize
Form Q with the normalized eigen vectors as columns
E.g. Diagonalize using an orthogonal matrix.
The eigen values are with eigen vector and with eigen vector
with and
Note that is an orthogonal set, so if we normalize it to , then we can use
with and D defined above.
Since is orthogonal, , so .
Def. Complex Numbers
In cartesian form,
In polar form,
The modulus is its magnitude
The principal argument, denoted , is if
The complex conjugate of is , and their product is a real number:
Thm is a real number iff
Proof Let for . Then .
Assume that is a real number. Then .
() Assume that . Then
E.g. Find the modulus and principal argument for
E.g. z = -1 + i. Express in the form a + bi where a and b are real numbers.
Def. De Moivre's Theorem
and where n is a positive integer
Def. nth roots of z
E.g. Solve
RHS is
RHS in polar form is
LHS in polar form is
Eq'n in polar form is
So and
k = 0
k = 1
k = 2
k = 4
Formulafor nth roots of :
for k = 0, 1, 2, …, n-1
E.g. Find the 4 fourth roots of 1.
Method 1: Factor and solve.
or .
Method 2: Use the formula.
E.g. Find eigen values/eigen vectors of
Def. Complex Vector Space
space of ordered n-tuples of complex numbers. Vectors in are . Assume scalars are in
Real scalars
Complex scalars
basis =
basis =
A complex vector space is one in which scalars are complex numbers.
E.g. is a complex vector space (with usual operations)
E.g. is not a complex vector space since it is not closed under scalar mult ()
E.g. If , find if is a basis of
Note is linearly independent since the matrix has rank 2.
Def. Conjugate Transpose
The conjugate transpose of A is defined as
Properties
Let A, B be m x n matrices and
if are square
Def. Euclidean Inner Product / Dot Product
In and
In
E.g. Find where and
Complex Dot Product Properties
Let
and iff
and
and
Def. Euclidean Norm
The Euclidean norm (or length) of is
Def. Unitary Matrix
A complex matrix is said to be unitary if any of the following is true (analogous to orthogonal matrices in )
columns of are orthonormal in
Property the product of unitary matrices is unitary.
Def. Hermitian Matrix
is a Hermitian matrix if (analogous to symmetric matrices in ).
It has real eigen values and is diagonalizable (by a unitary matrix).
Eigen vectors corresponding to distinct eigen values are orthogonal.
Proof (eigen values are real)
Let be an eigen value and be a Hermitian matrix.
Then for some
Since is Hermitian,
LHS:
RHS:
Equating LHS and RHS, we have that is real
Proof(eigen vectors are orthogonal)
Let be eigen values of with (nonzero) eigen vectors and , then
and , so
(If we take , , then which also proves the eigs are real)
Since the eigs are real,
So if , then
Proof(Hermitian iff )
() If , then
() Let . Then
Note if is skew-Hermitian(), then is Hermitian, and vice versa.
Fact Every square matrix can be decomposed into the sum of a Hermitian matrix and skew-Hermitian matrix
Def. Normal Matrix
A square matrix A is normal if it commutes with its conjugate transpose:
Property
If is normal, then
Proof
Shortcuts (to prove a matrix is normal)
Every Hermitian matrix is normal.
Proofsoand
Every unitary matrix is normal.
Proof so
Note for square matrices A and B, AB = I = BA always holds
Every skew-Hermitian matrix is normal.
Proofand
Def. Unitarily Diagonalizable
A square matrix is unitarily diagonalizable iff is a normal matrix.
E.g. Determine all values of such that is unitarily diagonalizable.
By thm, A must be normal, so
Calculate top left entry on both sides
Hence is any number such that
E.g. Find all such that the matrix is unitarily diagonalizable.
By thm, A must be normal, so
Hence is any number of the form such that
W10 (9.3)
Comparison - Real vs Complex
Real (Symmetric matrix)
Complex (Hermitian matrix)
eigen values of A are real
eigen values of H are real
eigen vectors corresponding to distinct eigen values are orthogonal in
eigen vectors corresponding to distinct eigen values are orthogonal in
there exists an orthogonal matrix s.t. is diagonal
there exists a unitary matrix s.t. is diagonal
Notes (eigenvalues)
If a matrix has odd order (order = m x n), then the eigen values must be real.
For a real matrix, eigen values come in conjugate pairs, i.e. if is an eigen value, then is also an eigen value.
For an orthogonal matrix, the eigen value pairs all lie on the unit circle.
For a Hermitian matrix, eigen values lie on the real axis; for a skew-Hermitian matrix, eigen values lie on the imaginary axis.
Proof (eigenvalues of skew-Hermitian matrices have form )
Let be an eigen vector for with corresponding eigen value
So
If we replace with , then we can prove that (eigen vectors corresp to dif eigen values are orthogonal)
Def. Schur's Theorem
If is an n x n complex matrix, then there must exist a unitary matrix s.t. is upper triangular. (The main diagonal of are eigenvalues of )
Def. Spectral Theorem
Recall Let A be an n x n real matrix. A is orthogonally diagonalizable iff A is symmetric.
Let A be an n x n complex matrix. A is unitarily diagonalizable iff A is normal.
Lemma If A is Hermitian, then there exists a unitary matrix such that is diagonal.
Proof By Schur's thm, there exists an upper triangular matrix .
Then
Since T is both upper triangular and lower triangular, it must be diagonal
Note The converse is false.
E.g. is not Hermitian but it is unitarily diagonalizable.
W11 (9.4)
Def. Jordan Canonical Form
Every n x n complex matrix is similar to a matrix of the following form ('s are not necessarily distinct).
The matrix is composed of Jordan blocks along the diagonal.
Def. Block Matrix
A block matrix is one that has been partitioned into blocks.
We can multiply block matrices (assuming sizes compatible):
Note that order matters!
A block diagonal matrix has square blocks down its diagonal. (JCF is block diagonal)
Its eigen values are exactly those of the blocks, and
E.g. Find the eigen values of
Observe that can be partitioned into 2 x 2 blocks.
The top left block has eigs , and the bottom right block has 2 and 4.
Properties of Jordan Blocks
Let be a k x k Jordan block
J has eigen value with algebraic mult k
Proof is a root with mult K
J is not diagonalizable unless k = 1 since (if k not = 1, the matrix is not diagonal)
Proof so
If P is the smallest positive integer such that , then
I.e. but if , then
Proof The 1's move up one line at a time when we take powers of
E.g. Let so k = 4
Fact
for
note that is an eigen vector with rank 1
Def. Generalized Eigenvector
For an n x n complex matrix , a generalized eigenvector with rank p is a non-zero vector corresponding to eigenvalue if for some positive integer p.
Generalized eigenspace: set of all generalized eigenvectors for plus .
Notes
ordinary eigenvectors are generalized eigenvectors with rank 1.
In general, if is not diagonalizable, then
But the generalized eigenspaces form a basis:
alg mult of
Why find generalized eigenvectors?
By forming P using generalized eigenvectors, we can turn into JCF using
E.g. Find generalized eigenvectors for
Eigen values are 1, 1, 3
When ,
When ,
where is a generalized eigen vector
Thm (Similar to JCF)
Every square complex matrix is similar to a JCF.
Properties
JCF is unique (up to permutation of blocks)
# blocks for is its geometric mult (each eigenvector of generates a block)
what happens for each is independent of other eigenvalues
E.g. If a 7 x 7 matrix has eigenvalues {1, 1, 1, 2, 2, 2, 2}, what are the possible JCF's?
For , the possible configurations are:
For , the possible configurations are:
For small order, the geo mult gives the block structure, but it does not tell us the structure for alg mult = 4, geo mult = 2 (see above underbrace). How do we tell which structure to use?
Compute for , i.e. generalized eigenspaces.
Note Each k x k Jordan block has
as eigen value with alg mult k and geo mult =
a chain of k generalized eigen vectors
NoteSolutions to are also solutions to
In general, an arbitrary matrix has a chain for each block in its JCF.
E.g. For a 5x5 matrix, an eigen value with alg mult = 5, geo mult = 3, we need 2 generalized eigenvectors:
3 chains – either 1 of them has 2 generalized eigenvectors, or 2 of them have 1 generalized eigenvector
E.g.
for the last one
E.g.
For the 1st block, we have the chain
For the 2nd block, we have the chain
are independent eigenvectors or rank 1
are independent generalized eigenvectors of rank 2
is an independent generalized eigenvector of rank 3
Put them into a matrix and
Fact# ind. gen. eigenvectors of rank at most k
since it has
since it has
since it has
Fact = # ind. gen. eigenvectors of rank k = # Jordan blocks of size
# of Jordan blocks of size k = (# Jordan blocks of size ) - (# Jordan blocks of size )
E.g. Find Jordan Form of if and suppose:
so # ind. gen. eigenvectors of rank at most 1 = 6
So is 13 x 13, with alg mult 13
Obtain 6 chains, each corresponding to a Jordan block (each eigen vector produces a Jordan block), and the length of the chain = size of the block
Use formula:
2(6) - 0 - 10 = 2 blocks of size 1
2(10) - 6 - 12 = 2 blocks of size 2
2(12) - 10 - 13 = 1 block of size 3
2(13) - 12 - 13 = 1 block of size 4
2(13) - 13 - 13 = 0 block of size 5
E.g. Is it possible for a matrix to have and
Def. Cayley Hamilton Thm
Every square matrix satisfies its own characteristic polynomial.